package leetcode.editor.cn;

import utils.PrintUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

//[18]四数之和
public class FourSum18 {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Solution solution = new FourSum18().new Solution();
        List<List<Integer>> lists = solution.fourSum(new int[]{-1,0,-5,-2,-2,-4,0,1,-2}, -9);
        //	Time Limit Exceeded
        //	测试用例:[-1,0,-5,-2,-2,-4,0,1,-2]
        //			-9
        //	stdout:自测 ok [-5, -4, -1, 1],[-5, -4, 0, 0],[-5, -2, -2, 0],[-4, -2, -2, -1],
//        List<List<Integer>> lists = solution.fourSum(new int[]{-2,0,5,-1,-5,5,3}, -2);
        //	Time Limit Exceeded
        //	测试用例:[-2,0,5,-1,-5,5,3]
        //			-2
        //	stdout:自测 ok [-5, -2, 0, 5],  leetcode !!!错误。
//        List<List<Integer>> lists = solution.fourSum(new int[]{2, 2, 2, 2}, 8);
        //	测试用例:[2,2,2,2,2]
        //			8
        //	测试结果:[[2,2,2,2],[2,2,2,2]]
        //	期望结果:[[2,2,2,2]]

//        List<List<Integer>> lists = solution.fourSum(new int[]{0, 1, 5, 0, 1, 5, 5, -4}, 11);
//        测试用例:[0,1,5,0,1,5,5,-4]
//        11
//        测试结果:[[-4,5,5,5]]
//        期望结果:[[-4,5,5,5],[0,1,5,5]]
        System.out.println("FourSum18:main:耗时："+(System.currentTimeMillis()-start)+"ms");
        PrintUtil.print(lists);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //        private List<List<Integer>> res = new ArrayList<>();//没有区别。
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums.length < 4) return res;

            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 1; i++) {
                if (i > 0 && (nums[i] == nums[i - 1])) continue;
                int tempTarget = target - nums[i];
                threeSum(res, nums, i + 1, nums.length - 1, tempTarget, nums[i]);
            }
            return res;
        }

        private void threeSum(List<List<Integer>> res, int[] nums, int l, int r, int target, int num4) {
            for (int i = l; i < nums.length - 1; i++) {
                if (i > l && (nums[i] == nums[i - 1])) continue;
                int tempTarget = target - nums[i];
                twoSum(res, nums, i + 1, nums.length - 1, tempTarget, num4, nums[i]);
            }
        }


        private void twoSum(List<List<Integer>> res, int[] nums, int l, int r, int target, int num4, int num3) {
            if (l >= r) return;
            // 失败 HashSet 因为重复的数，问题。 如果已经有序了，也可以 2 边向中间夹的方法。
            //这种方式失败，map 有重复的， 去重，之后 1 个结果也没了，2222==》[]
//            HashSet<Integer> num2Set = new HashSet<>();
//            for (int i = l; i <= r; i++) {
//                if (i > l && (nums[i] == nums[i - 1])) continue;//去重是否需要？
//
//                int num2 = target - nums[i];//target - num1 = num2
//                if (num2Set.contains(num2)) {
//                    //res
//                    res.add(Arrays.asList(num4, num3, num2, nums[i]));
//                }
//                num2Set.add(nums[i]);
//            }

            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum > target) {
                    r--;
                } else if (sum < target) {
                    l++;
                } else {
                    //res
                    res.add(Arrays.asList(num4, num3, nums[l], nums[r]));
                    //这里怎么去重 。eg: 222333
                    l++;
                    while (l<r && nums[l]==nums[l-1])l++;
                    r--;
                    while (l<r && nums[r]==nums[r+1])l--;
                }
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}